package com.java.恋上算法.数据结构._06_二叉搜索树;

import com.java.恋上算法.数据结构._06_二叉搜索树.printer.BinaryTreeInfo;
import com.java.恋上算法.数据结构._06_二叉搜索树.printer.BinaryTrees;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @desc: 二叉搜索树
 * @author: zhanghongqiang01@baijiahulian.com
 * @date: 2021/9/9/0009 下午 05:09
 */
public class BinarySearchTree<E> implements BinaryTreeInfo {
    private int size;
    private Node<E> root;

    private Comparator<E> comparator;

    public BinarySearchTree(){
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator){
        this.comparator = comparator;
    }



    public int size() // 元素的数量
    {
        return size;
    }

    public boolean isEmpty() // 是否为空
    {
        return size == 0;
    }

    public void clear() // 清空所有元素
    {

    }

    public void add(E element) // 添加元素
    {
        elementNotNullCheck(element);
        // 添加第一个节点
        if (root == null){
            root = new Node<>(element,null);
            size ++;
            return;
        }

        // 添加的不是第一个节点
        // 找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        do {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else { // 相等
                node.element = element;
                return;
            }
        } while (node != null);

        // 看看插入到父节点的那个位置
        Node<E> newNode = new Node<>(element,parent);
        if (cmp > 0){
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size ++;
    }

    public void remove(E element) // 删除元素
    {

    }

    public boolean contains(E element) // 是否包含某元素
    {
        return false;
    }





    /**
     * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
     */
    private int compare(E e1, E e2) {
        if (comparator != null){
            return comparator.compare(e1,e2);
        }
        return ((Comparable<E> )e1).compareTo(e2);
    }


    /**
     * 检测节点是否为空
     * @param element
     */
    private void elementNotNullCheck(E element){
        if (element == null){
            throw new IllegalArgumentException("element must not be null");
        }
    }


    public static abstract class   Visitor<E> {
        // 接口只允许定义方法
        // 抽象类允许有成员变量，抽象类有接口的感觉，在接口基础上又存储成员变量的功能

        boolean stop;
        /**
         * @return 如果返回true，就代表停止遍历
         */
        public abstract boolean visit(E element);
    }

    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element,Node<E> parent ){
            this.element = element;
            this.parent = parent;
        }
    }

    /**
     * 前序遍历
     */
    public void preorder (Visitor<E> visitor){
        if (visitor == null) {
            return;
        }
        preorder(root,visitor);
    }

    private void preorder(Node<E> node,Visitor<E> visitor){
        if (node == null || visitor.stop) {
            return;
        }

        visitor.stop = visitor.visit(node.element);
        preorder(node.left,visitor);
        preorder(node.right,visitor);
    }

    /**
     * 中序遍历
     */
    public void inorder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        inorder(root,visitor);
    }

    private void inorder(Node<E> node,Visitor<E> visitor){
        if (node == null || visitor.stop) {
            return;
        }

        inorder(node.left,visitor);
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        inorder(node.right,visitor);
    }

    /**
     * 后序遍历
     */
    public void postorder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        postorder(root,visitor);
    }

    private void postorder(Node<E> node,Visitor<E> visitor) {
        if (node == null) {
            return;
        }

        postorder(node.left,visitor);
        postorder(node.right,visitor);
        boolean stop=visitor.visit(node.element);
    }

    /**
     * 层序遍历
     * @param visitor
     */
    public void levelOrder(Visitor<E> visitor) {
        if (root == null || visitor == null) {
            return;
        }

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)){
                return;
            }

            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
        }
    }


//    /**
//     * 前序遍历
//     */
//    public void preorderTraversal (){
//        postorderTraversal(root);
//    }
//
//    private void preorderTraversal(Node<E> node){
//        if (node == null) {
//            return;
//        }
//
//        System.out.println(node.element);
//        postorderTraversal(node.left);
//        postorderTraversal(node.right);
//    }
//
//
//
//    /**
//     * 中序遍历
//     */
//    public void inorderTraversal() {
//        inorderTraversal(root);
//    }
//
//    private void inorderTraversal(Node<E> node){
//        if (node == null) {
//            return;
//        }
//        inorderTraversal(node.left);
//        System.out.println(node.element);
//        inorderTraversal(node.right);
//    }
//
//    /**
//     * 后序遍历
//     */
//    public void postorderTraversal() {
//        postorderTraversal(root);
//    }
//
//    private void postorderTraversal(Node<E> node) {
//        if (node == null) {
//            return;
//        }
//
//        postorderTraversal(node.left);
//        postorderTraversal(node.right);
//        System.out.println(node.element);
//    }
//
//    /**
//     * 层序遍历
//     */
//    public void levelOrderTranversal() {
//        if (root == null) {
//            return;
//        }
//
//        Queue<Node<E>> queue = new LinkedList<>();
//        queue.offer(root);
//
//        while (!queue.isEmpty()){
//            Node<E> node = queue.poll();
//            System.out.println(node.element);
//
//            if (node.left != null){
//                queue.offer(node.left);
//            }
//            if (node.right != null){
//                queue.offer(node.right);
//            }
//        }
//    }







    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
//        return ((Node<E>)node).element;

        Node<E> myNode = (Node<E>)node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }




}
